package everyday;

/**
 * @author zhangmin
 * @create 2022-04-25 13:24
 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
 *
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
 *
 * 问总共有多少条不同的路径？
 *
 * 思路：
 * 1、其实是一共要走m+n-2步，在这些步中，选m-1步为向下走，这样就可以用组合数来解决
 *  计算公式为：((m+n-2)(m+n-3)...n)/(m-1)!
 * 2、用回溯来遍历所有的路径
 */
public class uniquePaths62 {
    public int uniquePaths(int m, int n) {
        if (n==0) return 0;
        long res=1L;
        for (int i = m,j=1; j<n ; i++,j++) {
            res=res*i/j;
        }
        return (int) res;
    }
}
